package dfs;

import org.junit.Test;

import java.util.Arrays;

public class TwoSum1 {
    @Test
    public void test() {
        twoSum(new int[]{2,7,11,15}, 9);
        twoSum(new int[]{3,2,4}, 6);
        twoSum(new int[]{3,3}, 6);
    }

    static class Wrapper implements Comparable<Wrapper> {
        int index;
        int value;

        public Wrapper(int index, int value) {
            this.index = index;
            this.value = value;
        }

        @Override
        public int compareTo(Wrapper that) {
            return this.value - that.value;
        }

        public static Wrapper[] build(int[] nums) {
            Wrapper[] array = new Wrapper[nums.length];
            for (int i = 0; i < nums.length; i++) {
                array[i] = new Wrapper(i, nums[i]);
            }
            return array;
        }
    }

    // 返回下标, 排序之后乱了
    public int[] twoSum(int[] nums, int target) {
        Wrapper[] array = Wrapper.build(nums);
        Arrays.sort(array);

        int i = 0;
        int j = nums.length - 1;

        while (i < j) {
            int sum = array[i].value + array[j].value;
            if (sum == target) {
                System.out.format("nums: %s, target: %d, i, %d, index1: %d, j: %d, index2: %d\n", Arrays.toString(nums), target, i, array[i].index, j, array[j].index);
                return new int[]{array[i].index, array[j].index};
            }
            if (sum < target) {
                i++;
            } else {
                j--;
            }
        }
        return null;
    }
}
